Funkcje idempotentne (trudne słowo)

Limit pamięci: 64 MB

Dana jest liczba całkowita dodatnia . Oznaczmy przez zbiór . Funkcję nazywamy permutacją, jeśli jest różnowartościowa (dla różnych argumentów zwraca różne wartości). Funkcję nazywamy idempotentną, jeśli dla każdego zachodzi .

Dana jest funkcja . Ile jest różnych par funkcji takich, że:

• jest permutacją,
• jest idempotentna,
• dla każdego zachodzi ?

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę oraz opis funkcji ,
• wyznaczy liczbę par funkcji spełniających warunki zadania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (). Drugi wiersz zawiera opis funkcji - wartości () dla , pooddzielane pojedynczymi odstępami.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą: liczbę różnych par funkcji spełniających warunki zadania. Wynik należy wypisać modulo (tzn. podać resztę z dzielenia liczby tych funkcji przez ).

Przykład

Dla danych wejściowych:

8
7 4 5 1 7 4 4 1

poprawną odpowiedzią jest:

288

Autor zadania: Marcin Pilipczuk.